{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Palindromic Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestPalindromic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大回文数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个仅由数字（<code>0 - 9</code>）组成的字符串 <code>num</code> 。</p>\n",
    "\n",
    "<p>请你找出能够使用 <code>num</code> 中数字形成的 <strong>最大回文</strong> 整数，并以字符串形式返回。该整数不含 <strong>前导零</strong> 。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你 <strong>无需</strong> 使用 <code>num</code> 中的所有数字，但你必须使用 <strong>至少</strong> 一个数字。</li>\n",
    "\t<li>数字可以重新排序。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = \"444947137\"\n",
    "<strong>输出：</strong>\"7449447\"\n",
    "<strong>解释：</strong>\n",
    "从 \"<em><strong>44494</strong></em><em><strong>7</strong></em>13<em><strong>7</strong></em>\" 中选用数字 \"4449477\"，可以形成回文整数 \"7449447\" 。\n",
    "可以证明 \"7449447\" 是能够形成的最大回文整数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = \"00009\"\n",
    "<strong>输出：</strong>\"9\"\n",
    "<strong>解释：</strong>\n",
    "可以证明 \"9\" 能够形成的最大回文整数。\n",
    "注意返回的整数不应含前导零。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>num</code> 由数字（<code>0 - 9</code>）组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-palindromic-number](https://leetcode.cn/problems/largest-palindromic-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-palindromic-number](https://leetcode.cn/problems/largest-palindromic-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"444947137\"', '\"00009\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        c = Counter(num)\n",
    "        if len(c) == 1 and '0' in c: return '0' # 全为 0        \n",
    "        mid = ''\n",
    "        ans = ''\n",
    "        for x in '9876543210':\n",
    "            if c[x] % 2 and mid == '': mid = x # 确定中间数字\n",
    "            ans += x * (c[x] // 2)\n",
    "        i = 0 # 删除前导 0\n",
    "        while i < len(ans):\n",
    "            if ans[i] == '0': i += 1\n",
    "            else: break\n",
    "        ans = ans[i:]\n",
    "\n",
    "        return ans + mid + ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        c = Counter(num)\n",
    "        # 偶数次数的部分从大到小排列，单个奇数放最大值\n",
    "        ans = []\n",
    "        middle = ''\n",
    "        for k in sorted(c, reverse=True):\n",
    "            v = c[k]\n",
    "            if v > 1:\n",
    "                ans.append(k * (v >> 1))\n",
    "            if not middle and v & 1:\n",
    "                middle = k\n",
    "        if len(ans) == 1 and ans[0][0] == '0':\n",
    "            return middle or '0'\n",
    "        return ''.join(ans + [middle] + ans[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        d = {}\n",
    "        for c in num:\n",
    "            if c in d:\n",
    "                d[c] += 1\n",
    "            else:\n",
    "                d[c] = 1\n",
    "        s = ''\n",
    "        x = ''\n",
    "        for c in '987654321':\n",
    "            if c in d:\n",
    "                s += c * (d[c] // 2)\n",
    "                if x == '' and d[c] % 2 == 1:\n",
    "                    x = c\n",
    "        if '0' in d:\n",
    "            if s:\n",
    "                s += '0' * (d['0'] // 2)\n",
    "                if x == '' and d['0'] % 2 == 1:\n",
    "                    x = '0'\n",
    "            else:\n",
    "                if x == '':\n",
    "                    x = '0'\n",
    "        return s + x + s[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        ans = 0\n",
    "        cnt = [0] * 10\n",
    "        ch = ''\n",
    "        res = \"\"\n",
    "        for x in num:\n",
    "            cnt[int(x)] += 1\n",
    "        for i in range(9, -1, -1):\n",
    "            if i == 0 and len(res) == 0:\n",
    "                if ch != '':\n",
    "                    return ch * cnt[int(ch)]\n",
    "                else:\n",
    "                    return \"0\"\n",
    "            res += str(i) * (cnt[i] // 2)\n",
    "            if cnt[i] % 2 == 1 and ch == '':\n",
    "                ch = str(i)\n",
    "        return res + ch + res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(num)\n",
    "        if cnt['0'] == len(num):  # 特判最特殊的情况：num 全是 0\n",
    "            return \"0\"\n",
    "\n",
    "        s = \"\"\n",
    "        for d in digits[:0:-1]:\n",
    "            s += d * (cnt[d] // 2)\n",
    "        if s:  # 如果填了数字，则可以填 0\n",
    "            s += '0' * (cnt['0'] // 2)\n",
    "\n",
    "        t = s[::-1]\n",
    "        for d in digits[::-1]:\n",
    "            if cnt[d] % 2:  # 还可以填一个变成奇回文串\n",
    "                s += d\n",
    "                break\n",
    "        return s + t  # 添加镜像部分\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt  = Counter(num)\n",
    "        if cnt['0'] == len(num):\n",
    "            return '0'\n",
    "        s = \"\"\n",
    "        for d in digits[:0:-1]:\n",
    "            s += d * (cnt[d] //2)\n",
    "        if s :\n",
    "            s += '0' * (cnt['0'] //2)\n",
    "\n",
    "        t = s[::-1]\n",
    "        for d in digits[::-1]:\n",
    "            if cnt[d] % 2:\n",
    "                s += d\n",
    "                break\n",
    "        return s + t "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        num_counter = Counter(num)    #统计各数字出现个数\n",
    "        if num_counter['0'] == len(num):   # 0的个数=数组长度，即num中去全是0的情况\n",
    "            return '0'\n",
    "\n",
    "        s = ''   #创建空字符串\n",
    "        for d in digits[:0:-1]:   #0-9倒序输出，前闭后开，0取不到\n",
    "            s = s + d*(num_counter[d] // 2)   #遍历9~1，如果num中存在该数字d，则用它的出现次数num_counter[d]÷2，添加进字符串中.不存在则无法添加\n",
    "        if s:\n",
    "            s += '0'*(num_counter['0'] // 2)    #添加了数字以后才考虑0，0放在最后，保证得出来的字符串最大且不存在前导0\n",
    "                                                #至此，s为回文数前半部分\n",
    "\n",
    "        t = s[::-1]   #倒序输出s,则t为后半回文数\n",
    "        for d in digits[::-1]:\n",
    "            if num_counter[d] % 2 :   #重新读取9-0，将第一个读取到的只出现一次的数加入中间\n",
    "                s+=d                  #变成奇数回文数，使结果更大\n",
    "                break\n",
    "        \n",
    "        return s+t  #返回回文数\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(num)\n",
    "        cnt = sorted(cnt.items(), key=lambda x: -ord(x[0]))\n",
    "        ret = ''\n",
    "        flag = True\n",
    "        for k, v in cnt:\n",
    "            if v & 1 and flag:\n",
    "                ret += k\n",
    "                flag = False\n",
    "            else:\n",
    "                ret += k * (v >> 1)\n",
    "        ret = str(int(ret[::-1]))\n",
    "        ret = ret[::-1]\n",
    "        if flag:\n",
    "            ret += ret[::-1]\n",
    "        else:\n",
    "            ret = ret[1:] + ret[0] + ret[1:][::-1]\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        if len(num) == num.count('0'): return '0'\n",
    "        cnt = list(map(list, sorted(Counter(num).items(), key=lambda x: -ord(x[0]))))\n",
    "        even = odd = ''\n",
    "        for i in range(len(cnt)):\n",
    "            if cnt[i][-1] > 1:\n",
    "                even += cnt[i][-1] // 2 * cnt[i][0]\n",
    "                cnt[i][-1] %= 2\n",
    "            if cnt[i][-1] == 1:\n",
    "                odd = max(odd, cnt[i][0])\n",
    "        if len(even) == even.count('0'): even = ''\n",
    "        return even + odd * (len(odd)) + even[::-1]\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(num)\n",
    "        if cnt['0'] == len(num): return \"0\"\n",
    "        s = \"\"\n",
    "        for i in range(9, 0, -1):\n",
    "            s += cnt[str(i)] // 2 * str(i)\n",
    "        if s:\n",
    "            s += \"0\" * (cnt['0'] // 2)\n",
    "        t = s[::-1]\n",
    "        for j in range(9, -1, -1):\n",
    "            if cnt[str(j)] % 2:\n",
    "                s += str(j)\n",
    "                break\n",
    "        return s + t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(num)\n",
    "        cnt = sorted(cnt.items(), key=lambda x: -ord(x[0]))\n",
    "        ret = ''\n",
    "        flag = True\n",
    "        for k, v in cnt:\n",
    "            if v & 1 and flag:\n",
    "                ret += k\n",
    "                flag = False\n",
    "            else:\n",
    "                ret += k * (v >> 1)\n",
    "        ret = str(int(ret[::-1]))\n",
    "        ret = ret[::-1]\n",
    "        if flag:\n",
    "            ret += ret[::-1]\n",
    "        else:\n",
    "            ret = ret[1:] + ret[0] + ret[1:][::-1]\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        if len(num) == num.count('0'): return '0'\n",
    "        cnt = Counter(num)\n",
    "        cnt = list(map(list, sorted(cnt.items(), key=lambda x: -ord(x[0]))))\n",
    "        even = ''\n",
    "        odd = ''\n",
    "        for i, (x, y) in enumerate(cnt):\n",
    "            if y > 1:\n",
    "                even += y // 2 * x\n",
    "                cnt[i][-1] %= 2\n",
    "            if cnt[i][-1] == 1:\n",
    "                odd = max(odd, x)\n",
    "        if len(even) == even.count('0'):\n",
    "            even = ''\n",
    "        if odd:\n",
    "            even += odd + even[::-1]\n",
    "        else:\n",
    "            even += even[::-1]\n",
    "        return even"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = [0] * 10\n",
    "        for x in num:\n",
    "            cnt[ord(x) - ord('0')] += 1\n",
    "        half = ''\n",
    "        middle = ''\n",
    "        for i in range(9, -1, -1):\n",
    "            if i != 0 or half:\n",
    "                half += str(i) * (cnt[i] >> 1)\n",
    "            if cnt[i] & 1 and middle == '':\n",
    "                middle = str(i)\n",
    "       \n",
    "        ret = half + middle + half[::-1]\n",
    "        if ret == '':\n",
    "            ret = '0'\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        mapping = {}\n",
    "        for c in num:\n",
    "            if(c not in mapping):\n",
    "                mapping[c] = 1\n",
    "            else:\n",
    "                mapping[c] += 1\n",
    "        center = None\n",
    "        result = ''\n",
    "        for d in range(10):\n",
    "            digit = str(d)\n",
    "            if(digit not in mapping):\n",
    "                continue\n",
    "            if(mapping[digit] % 2 == 1):\n",
    "                center = digit\n",
    "            cnt = mapping[digit] // 2\n",
    "            result = cnt*digit + result + cnt*digit\n",
    "        if(center):\n",
    "            result = result[:len(result)//2] + center + result[len(result)//2:]\n",
    "        if(result[0] == '0'):\n",
    "            zero = mapping['0']//2\n",
    "            result = result[zero:-zero] if result[zero:-zero] != '' else '0'\n",
    "        return result\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        ans = ''\n",
    "        from collections import Counter\n",
    "        cnt = Counter(num)\n",
    "        if cnt['0'] == len(num):\n",
    "            return '0'\n",
    "        for d in '987654321':\n",
    "            ans += d * (cnt[d] // 2)\n",
    "        if ans:\n",
    "            ans += '0' * (cnt['0'] // 2)\n",
    "        b=ans[::-1]\n",
    "        for d in '9876543210':\n",
    "            if cnt[d] % 2:\n",
    "                ans += d\n",
    "                break\n",
    "        return ans + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt=collections.Counter(num)\n",
    "        zero=\"\"\n",
    "        F0=0\n",
    "        fe=0\n",
    "        first=\"\"\n",
    "        last=\"\"\n",
    "        mid=\"\"\n",
    "        #print()\n",
    "\n",
    "        for x in [str(i) for i in range(9,0,-1)]:\n",
    "            if cnt[x]==0:\n",
    "                continue\n",
    "            if cnt[x]%2==0:\n",
    "                first=first+x*(cnt[x]//2)\n",
    "                last=x*(cnt[x]//2)+last\n",
    "            elif cnt[x]%2!=0 and fe==0:\n",
    "                mid=x\n",
    "                fe=1\n",
    "                if cnt[x]-1>0:\n",
    "                    y=cnt[x]-1\n",
    "                    first=first+x*(y//2)\n",
    "                    last=x*(y//2)+last\n",
    "            elif cnt[x]%2!=0 and fe!=0:\n",
    "                if cnt[x]-1>0:\n",
    "                    y=cnt[x]-1\n",
    "                    first=first+x*(y//2)\n",
    "                    last=x*(y//2)+last\n",
    "        if cnt[\"0\"]%2==0 and cnt[\"0\"]!=0:\n",
    "            if len(first)!=0:\n",
    "                first=first+\"0\"*(cnt[\"0\"]//2)\n",
    "                last=\"0\"*(cnt[\"0\"]//2)+last\n",
    "            elif len(first)==0 and len(mid)==0:\n",
    "                mid=\"0\"\n",
    "        elif cnt[\"0\"]%2!=0 and cnt[\"0\"]!=0:\n",
    "            if len(mid)==0 and len(first)==0:\n",
    "                mid=\"0\"\n",
    "            elif len(mid)==0 and len(first)!=0:\n",
    "                mid=\"0\"*cnt[\"0\"]\n",
    "            elif cnt[\"0\"]-1>0 and len(first)!=0:\n",
    "                y=cnt[\"0\"]-1\n",
    "               # print(y)\n",
    "                first=first+\"0\"*(y//2)\n",
    "                last=\"0\"*(y//2)+last\n",
    "     \n",
    "        return first+mid+last\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        mapping = {}\n",
    "        for c in num:\n",
    "            if(c not in mapping):\n",
    "                mapping[c] = 1\n",
    "            else:\n",
    "                mapping[c] += 1\n",
    "        if('0' in mapping):\n",
    "            zero = mapping['0']//2\n",
    "        center = None\n",
    "        result = ''\n",
    "        for d in range(10):\n",
    "            digit = str(d)\n",
    "            if(digit not in mapping):\n",
    "                continue\n",
    "            if(mapping[digit] % 2 == 1):\n",
    "                center = digit\n",
    "            cnt = mapping[digit] // 2\n",
    "            result = cnt*digit + result + cnt*digit\n",
    "        if(center):\n",
    "            result = result[:len(result)//2] + center + result[len(result)//2:]\n",
    "        if(result[0] == '0'):\n",
    "            result = result[zero:-zero] if result[zero:-zero] != '' else '0'\n",
    "        return result\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(num)\n",
    "        if cnt['0'] == len(num):\n",
    "            return '0'\n",
    "\n",
    "        \n",
    "        s = \"\"\n",
    "        # 从数字9-1逆序添加，就不用对cnt排序\n",
    "        for d in digits[:0:-1]: \n",
    "            s += d*(cnt[d] // 2)\n",
    "        if s:\n",
    "            s+= '0' * (cnt['0'] // 2)\n",
    "        t = s[::-1]\n",
    "        for d in digits[::-1]:\n",
    "            if cnt[d] % 2 != 0:\n",
    "                s += d\n",
    "                break\n",
    "        return s+t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        if not num.strip(\"0\"):\n",
    "            return \"0\"\n",
    "        from collections import defaultdict\n",
    "        count_dict = defaultdict(int)\n",
    "        for n in num:\n",
    "            count_dict[n] += 1\n",
    "        result = \"\"\n",
    "        for n in \"0123456789\":\n",
    "            if count_dict[n] > 1:\n",
    "                c = count_dict[n]//2\n",
    "                result = n*c + result + n*c\n",
    "                count_dict[n] -= c*2\n",
    "        has_sigle = False\n",
    "        for n in \"9876543210\":\n",
    "            if count_dict[n] > 0:\n",
    "                has_sigle = True\n",
    "                break\n",
    "        if has_sigle:\n",
    "            half = len(result)//2\n",
    "            result = (result[:half] + n + result[half:]).strip(\"0\")\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        numCnt = collections.Counter(num)\n",
    "        \n",
    "        medium = \"\"\n",
    "        ans = []\n",
    "        for i in range(9, 0, -1):\n",
    "            if numCnt[str(i)]:\n",
    "                if numCnt[str(i)] // 2:\n",
    "                    ans.append(str(i) * (numCnt[str(i)] // 2))\n",
    "                if numCnt[str(i)] % 2 and not medium:\n",
    "                    medium = str(i)\n",
    "\n",
    "        if numCnt[\"0\"]:\n",
    "            if not ans: \n",
    "                return \"0\" if not medium else medium\n",
    "            else:\n",
    "                ans.append(\"0\" * (numCnt[\"0\"] // 2))\n",
    "                if numCnt[\"0\"] % 2 and not medium:\n",
    "                    medium = \"0\"\n",
    "        return \"\".join(ans) + medium + \"\".join(ans[::-1])        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        char = [0] * 10\n",
    "        for c in num:\n",
    "            char[int(c)] += 1\n",
    "        res = \"\"\n",
    "        for i in range(9,0,-1):\n",
    "            res += str(i) * (char[i] // 2)\n",
    "            char[i] -= char[i] // 2 * 2\n",
    "        if len(res) > 0:\n",
    "            res += \"0\" * (char[0] // 2)\n",
    "            char[0] -= char[0] // 2 * 2\n",
    "        mid = \"\"\n",
    "        for i in range(9, -1, -1):\n",
    "            if char[i] > 0:\n",
    "                mid = str(i)\n",
    "                break\n",
    "        return res + mid + res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        #if int(num.strip('0')) < 10: return num.strip('0')\n",
    "        ans, pro = \"\", \"\"\n",
    "        dic = dict(collections.Counter(num))\n",
    "        if len(dic) == 1 and '0' in dic: return '0'\n",
    "        dic2 = sorted(dic.items(), key=lambda x:(x[0]), reverse=True)\n",
    "        for ch in dic2:\n",
    "            if ch[1] % 2 == 0:\n",
    "                ans += ch[0] * (ch[1] // 2)\n",
    "            else:\n",
    "                if ch[1] > 2:\n",
    "                    ans += ch[0] * (ch[1] // 2)\n",
    "                pro += ch[0]\n",
    "        ans = ans.lstrip('0')\n",
    "        if pro == \"\":\n",
    "            return ans + ans[::-1]\n",
    "        else:\n",
    "            return ans + pro[0] + ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        nums = [0] * 10\n",
    "        for n in num:\n",
    "            nums[int(n)] += 1\n",
    "        left, right = '', ''\n",
    "        max_num = -1\n",
    "        for n in range(len(nums)-1, 0, -1):\n",
    "            if nums[n] % 2 == 1:\n",
    "                max_num = max(n, max_num)\n",
    "            ss = f'{n}' *( nums[n] // 2)\n",
    "            left = left + ss\n",
    "            right = ss + right\n",
    "        if len(left) > 0:\n",
    "            if nums[0] % 2 == 1:\n",
    "                max_num = max(0, max_num)\n",
    "            ss = f'0' *( nums[0] // 2)\n",
    "            left = left + ss\n",
    "            right = ss + right\n",
    "        elif nums[0] > 0:\n",
    "            max_num = max(max_num, 0)\n",
    "        if max_num != -1:\n",
    "            return f\"{left}{max_num}{right}\" \n",
    "        return f\"{left}{right}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(num)\n",
    "        res = deque()\n",
    "\n",
    "        tmp = max([i for i, v in cnt.items() if v % 2 == 1], default=None)\n",
    "        if tmp: res.append(tmp)\n",
    "\n",
    "        for i in sorted([i for i, v in cnt.items() if v > 1]):\n",
    "            n = cnt[i] >> 1\n",
    "            res.appendleft(i * n)\n",
    "            res.append(i * n)\n",
    "\n",
    "        while len(res) >= 2 and res[0].startswith('0'):\n",
    "            res.popleft()\n",
    "            res.pop()\n",
    "\n",
    "        return ''.join(res) if res else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        count = Counter(num)\n",
    "\n",
    "        if count[\"0\"]==len(num):\n",
    "            return \"0\"\n",
    "\n",
    "        s = \"\"\n",
    "        for i in digits[:0:-1]:\n",
    "            s += i*(count[i]//2)\n",
    "        if s:\n",
    "            s += \"0\"*(count[\"0\"]//2)\n",
    "        a = \"\"\n",
    "        t = s[::-1]\n",
    "        for i in digits[::-1]:\n",
    "            if count[i]%2 == 1:\n",
    "                a = i\n",
    "                break\n",
    "        return s+a+t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(num)\n",
    "        if cnt['0'] == len(num):  # 特判最特殊的情况：num 全是 0\n",
    "            return \"0\"\n",
    "\n",
    "        s = \"\"\n",
    "        for d in digits[:0:-1]:\n",
    "            s += d * (cnt[d] // 2)\n",
    "        if s:  # 如果填了数字，则可以填 0\n",
    "            s += '0' * (cnt['0'] // 2)\n",
    "\n",
    "        t = s[::-1]\n",
    "        for d in digits[::-1]:\n",
    "            if cnt[d] % 2:  # 还可以填一个变成奇回文串\n",
    "                s += d\n",
    "                break\n",
    "        return s + t  # 添加镜像部分\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(num)\n",
    "        if cnt['0'] == len(num):\n",
    "            return \"0\"\n",
    "        s = \"\"\n",
    "        for i in range(9, 0, -1):\n",
    "            s += str(i) * (cnt[str(i)] // 2)\n",
    "        if s:\n",
    "            s += \"0\" * (cnt['0'] // 2)\n",
    "        t = s[::-1]\n",
    "        for j in range(9, -1, -1):\n",
    "            if cnt[str(j)] % 2:\n",
    "                s += str(j)\n",
    "                break\n",
    "        return s + t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(num)\n",
    "        single = \"\"\n",
    "        ans = \"\"\n",
    "        for i in range(9, 0, -1):\n",
    "            x = cnt[str(i)]\n",
    "            ans += str(i)*(x//2)\n",
    "            if x % 2 and not single:\n",
    "                single = str(i)\n",
    "        if ans:\n",
    "            x = cnt[str(0)]\n",
    "            ans += str(0)*(x//2)\n",
    "            if x % 2 and not single:\n",
    "                single = str(0)\n",
    "            return ans + single + ans[::-1]\n",
    "        if single:\n",
    "            return single\n",
    "        return \"0\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(num)      # 统计各字符数目\n",
    "        res = []\n",
    "        \n",
    "        # 回文半径字符【偶数，对称】\n",
    "        for i in range(9, -1, -1):          # 从大到小遍历\n",
    "            if i == 0 and len(res) == 0:    # 回文数为空，不能添加00\n",
    "                continue\n",
    "            ch = str(i)\n",
    "            k = cnt[ch]\n",
    "            if k >= 2:\n",
    "                res.append(ch * (k//2))\n",
    "                cnt[ch] -= (k//2) * 2\n",
    "        \n",
    "        # 回文长度为奇数：添加回文中心字符【若存在，只能添加一个，择最大者】\n",
    "        for i in range(9, -1, -1):\n",
    "            ch = str(i)\n",
    "            if cnt[ch] > 0:           # 可添加当前字符为回文中心，并返回答案\n",
    "                return ''.join(res) + ch + ''.join(res[::-1])\n",
    "        \n",
    "        # 回文长度为偶数：无中心字符\n",
    "        return ''.join(res) + ''.join(res[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        nums = [0] * 10\n",
    "        for s in num:\n",
    "            nums[int(s)] += 1\n",
    "        ans = \"\"\n",
    "        z = -1\n",
    "        for i in range(9, 0, -1):\n",
    "            if nums[i] // 2 != 0:\n",
    "                ans += str(i)*(nums[i] // 2)\n",
    "            if nums[i] % 2 == 1 and z== -1:\n",
    "                z=i\n",
    "        \n",
    "        if ans != \"\" and nums[0] // 2 != 0:\n",
    "            ans += str(0)*(nums[0] // 2)\n",
    "        if nums[0] % 2 == 1 and z== -1:\n",
    "            z=0\n",
    "        if ans == \"\" and nums[0] != 0 and (z == -1 or z == 0):\n",
    "            return \"0\"\n",
    "        elif z != -1:\n",
    "            return ans+str(z)+ans[::-1]\n",
    "        else:\n",
    "            return ans+ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        import collections\n",
    "        cnt = collections.Counter(num)\n",
    "        if cnt['0'] == len(num):\n",
    "            return '0'\n",
    "        s = ''\n",
    "        for d in '987654321':\n",
    "            s += d * (cnt[d] // 2)\n",
    "        if s:\n",
    "            s += '0' * (cnt['0'] // 2)\n",
    "\n",
    "        t = s[::-1]\n",
    "        for d in '9876543210':\n",
    "            if cnt[d] % 2:\n",
    "                s += d\n",
    "                break\n",
    "        return s + t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        #if int(num.strip('0')) < 10: return num.strip('0')\n",
    "        ans, pro = \"\", \"\"\n",
    "        dic = dict(collections.Counter(num))\n",
    "        if len(dic) == 1 and '0' in dic: return '0'\n",
    "        dic2 = sorted(dic.items(), key=lambda x:(x[0]), reverse=True)\n",
    "        for ch in dic2:\n",
    "            if ch[1] % 2 == 0:\n",
    "                ans += ch[0] * (ch[1] // 2)\n",
    "            else:\n",
    "                if ch[1] > 2:\n",
    "                    ans += ch[0] * (ch[1] // 2)\n",
    "                pro += ch[0]\n",
    "        ans = ans.lstrip('0')\n",
    "        if pro == \"\":\n",
    "            return ans + ans[::-1]\n",
    "        else:\n",
    "            return ans + pro[0] + ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        counter = Counter(num)\n",
    "        digits=[\"0\",\"1\",\"2\",\"3\",\"4\",\"5\",\"6\",\"7\",\"8\",\"9\"]\n",
    "        if counter[\"0\"]  ==len(num):\n",
    "            return \"0\"\n",
    "        s = \"\"\n",
    "        for d in digits[:0:-1]:\n",
    "            s += d * (counter[d] // 2)\n",
    "        if s:\n",
    "            s += \"0\" * (counter[\"0\"] // 2)\n",
    "        t = s[::-1]\n",
    "        for d in digits[::-1]:\n",
    "            if counter[d] % 2:\n",
    "                s += d\n",
    "                break\n",
    "        return s + t\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        nums = [0] * 10\n",
    "        for s in num:\n",
    "            nums[int(s)] += 1\n",
    "        ans = \"\"\n",
    "        z = -1\n",
    "        for i in range(9, 0, -1):\n",
    "            if nums[i] // 2 != 0:\n",
    "                ans += str(i)*(nums[i] // 2)\n",
    "            if nums[i] % 2 == 1 and z== -1:\n",
    "                z=i\n",
    "        \n",
    "        if ans != \"\" and nums[0] // 2 != 0:\n",
    "            ans += str(0)*(nums[0] // 2)\n",
    "        if nums[0] % 2 == 1 and z== -1:\n",
    "            z=0\n",
    "        if ans == \"\" and nums[0] != 0 and z == -1:\n",
    "            return \"0\"\n",
    "        elif z != -1:\n",
    "            return ans+str(z)+ans[::-1]\n",
    "        else:\n",
    "            return ans+ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(num)\n",
    "        ans = ['', '', '']\n",
    "        for i in range(9, -1, -1):\n",
    "            c = str(i)\n",
    "            if c != '0' or (c == '0' and ans[0]):\n",
    "                ans[0] += c * (cnt[c] // 2)\n",
    "                ans[-1] = c * (cnt[c] // 2) + ans[-1]\n",
    "                cnt[c] %= 2\n",
    "        for i in range(9, -1, -1):\n",
    "            c = str(i)\n",
    "            if cnt[c]:\n",
    "                ans[0] += c\n",
    "                break\n",
    "        \n",
    "                \n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        from collections import Counter\n",
    "        even_nums = [k for k,v in Counter(num).items() if v%2==1]\n",
    "        even_nums = max(even_nums) if even_nums else \"\"\n",
    "        odd_nums = []\n",
    "        [odd_nums.extend([k]*(int(v)//2)) for k,v in Counter(num).items() if v>=2]\n",
    "        odd_nums.sort(reverse=True)\n",
    "        odd_nums = \"\".join(odd_nums)\n",
    "        result = odd_nums + even_nums + odd_nums[::-1] if set(odd_nums) != set('0') else even_nums\n",
    "        result = result if result else \"0\"\n",
    "        return result\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = [0] * 10\n",
    "        for n in num:\n",
    "            cnt[ord(n) - ord('0')] += 1\n",
    "        if cnt[0] == len(num):\n",
    "            return '0'\n",
    "        \n",
    "        cnt1 = cnt[1:]\n",
    "\n",
    "        if all([d == 1 or d == 0 for d in cnt1]):\n",
    "            for i in range(9, -1, -1):\n",
    "                if cnt[i] != 0:\n",
    "                    return str(i)\n",
    "        \n",
    "        fP, sP = \"\" , \"\"\n",
    "        longestOdd = -1\n",
    "\n",
    "        for i in range(9, -1, -1):\n",
    "            x = cnt[i] // 2\n",
    "            fP += str(i) * x\n",
    "            cnt[i] -= 2 * x\n",
    "        \n",
    "        for i in range(9, -1, -1):\n",
    "            if cnt[i] % 2 == 1 and cnt[i] > longestOdd:\n",
    "                sP = str(i) * cnt[i]\n",
    "                longestOdd = cnt[i]\n",
    "        \n",
    "        return fP + sP + fP[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt, ans = [0] * 10, \"\"\n",
    "        for c in num:\n",
    "            cnt[ord(c) - ord('0')] += 1\n",
    "        for i in range(9, -1, -1):\n",
    "            ans += ''.join(chr(ord('0') + i) for _ in range(cnt[i] >> 1))\n",
    "        first = next((chr(ord('0') + i) for i in range(9, -1, -1) if cnt[i] & 1), '')\n",
    "        if not ans: return first\n",
    "        if ans[0] == '0': return first if first else '0'\n",
    "        return ans + first + ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        m = defaultdict(int)\n",
    "        for c in num:\n",
    "            m[c] += 1\n",
    "        \n",
    "        first_part = \"\" # 前半部分\n",
    "\n",
    "        for i in range(9, -1, -1): # 贪心，从大到小枚举偶数的数字，append到结果上面去\n",
    "\n",
    "            # 避免前导0\n",
    "            if i == 0 and first_part == \"\":\n",
    "                break\n",
    "\n",
    "            cnt = m[str(i)] // 2\n",
    "\n",
    "            for j in range(cnt):\n",
    "                first_part += str(i)\n",
    "            \n",
    "            m[str(i)] -= 2*cnt # 减去使用次数\n",
    "        \n",
    "        second_part = first_part[::-1] # 后半边\n",
    "\n",
    "        # 遍历剩下的字符，如果还有，取一个最大的，放到中间（前半部分的后面）\n",
    "        for i in range(9, -1, -1):\n",
    "            if m[str(i)] > 0:\n",
    "                first_part += str(i)\n",
    "                break\n",
    "        \n",
    "        return first_part + second_part\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        num = list(num)\n",
    "        a = [0,0,0,0,0,0,0,0,0,0]\n",
    "        c = Counter(num)\n",
    "        ans=''\n",
    "        for key,value in c.items():\n",
    "            a[int(key)]=value\n",
    "        for i in range(len(a)-1,-1,-1):\n",
    "            ans+=str(i)*(a[i]//2)\n",
    "            a[i]%=2\n",
    "        flag=0\n",
    "        for i in range(len(a)-1,-1,-1):\n",
    "            if a[i]==1:\n",
    "                ans+=str(i)\n",
    "                flag=1\n",
    "                break\n",
    "        ans+=ans[-1-flag::-1]\n",
    "        ans = ans.strip('0')\n",
    "        if ans=='':\n",
    "            ans = max(num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        c=collections.Counter(num)\n",
    "        ret=\"\"\n",
    "        for i in range(9,-1,-1):\n",
    "            now=chr(ord(\"0\")+i)\n",
    "            if now==\"0\" and not ret:\n",
    "                continue\n",
    "            if c[now]>=2:\n",
    "                ret+=now*(c[now]//2)\n",
    "                c[now]%=2\n",
    "        mid=\"\"\n",
    "        for i in range(9,-1,-1):\n",
    "            now=chr(ord(\"0\")+i)\n",
    "            if c[now]!=0:\n",
    "                mid=now\n",
    "                break\n",
    "        return ret+mid+ret[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num):\n",
    "        pri={}\n",
    "        rest={}\n",
    "        for i in num:\n",
    "            if (int(i) not in rest.keys()) and (int(i) not in pri.keys()):\n",
    "                rest[int(i)]=1\n",
    "            elif (int(i) in rest.keys()) and (int(i) not in pri.keys()):\n",
    "                del rest[int(i)]\n",
    "                pri[int(i)]=2\n",
    "            elif (int(i) not in rest.keys()) and (int(i) in pri.keys()):\n",
    "                pri[int(i)]+=1\n",
    "\n",
    "        result=\"\"\n",
    "        while pri.keys():\n",
    "            max_letter=max(pri.keys())\n",
    "            #print(max_letter)\n",
    "            pri[max_letter]-=2\n",
    "\n",
    "            if pri[max_letter]==1:\n",
    "                rest[max_letter]=1\n",
    "                del pri[max_letter]\n",
    "            elif pri[max_letter]==0:\n",
    "                del pri[max_letter]\n",
    "            #print(pri)\n",
    "            if len(result)==0:\n",
    "                if max_letter==0 and rest:\n",
    "                    continue\n",
    "                elif max_letter==0 and not rest:\n",
    "                    return \"0\"\n",
    "                result=str(max_letter)+str(max_letter)\n",
    "\n",
    "            else:\n",
    "                #print(result)\n",
    "                result=result[0:int((len(result)/2))]+str(max_letter)+str(max_letter)+result[int((len(result)/2)):]\n",
    "                #print(result)\n",
    "\n",
    "            #print(result)\n",
    "\n",
    "        #print(rest)\n",
    "        if rest:\n",
    "            max_letter_rest=max(rest.keys())\n",
    "            result=result[0:int((len(result)/2))]+str(max_letter_rest)+result[int((len(result)/2)):]\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        \n",
    "        n = len(num)\n",
    "        \n",
    "        counter = Counter(num)\n",
    "        counter = sorted(\n",
    "            counter.items(), \n",
    "            key=lambda elem: -int(elem[0])\n",
    "        )\n",
    "        \n",
    "        if len(counter) == 1:\n",
    "            return '0' if num[0] == '0' else num\n",
    "        \n",
    "        prefix, mid = '', ''\n",
    "\n",
    "        for ch, cnt in counter:\n",
    "            if cnt % 2 == 1 and mid == '':\n",
    "                mid = ch\n",
    "                \n",
    "            if cnt // 2 != 0:\n",
    "                prefix += ch * (cnt // 2)\n",
    "        \n",
    "        if prefix and prefix[0] == '0':\n",
    "            idx = prefix.rfind('0')\n",
    "            prefix = prefix[idx + 1:]\n",
    "\n",
    "        res = prefix + mid + prefix[::-1]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        if num == len(num) * '0': return '0'\n",
    "        cnt = [0] * 10\n",
    "        for s in num:\n",
    "            cnt[ord(s) - ord('0')] += 1\n",
    "        temp = None\n",
    "        s = ''\n",
    "        for i in range(len(cnt)-1, -1, -1):\n",
    "            if cnt[i] % 2 == 1 and temp == None:\n",
    "                temp = str(i)\n",
    "            s += cnt[i] // 2 * str(i) if not (i == 0 and s == '') else ''\n",
    "        return s + s[::-1] if temp == None else s + temp + s[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(num)\n",
    "        if cnt['0'] == len(num):\n",
    "            return \"0\"\n",
    "        s = \"\"\n",
    "        for d in digits[:0:-1]:\n",
    "            s+=d*(cnt[d]//2)\n",
    "        if s:  # 如果填了数字，则可以填0\n",
    "            s+= '0'*(cnt['0']//2)\n",
    "        \n",
    "        t = s[::-1]\n",
    "        for d in digits[::-1]:\n",
    "            if cnt[d]%2:\n",
    "                s+=d \n",
    "                break \n",
    "        return s+t "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt, ans = [0] * 10, \"\"\n",
    "        for c in num:\n",
    "            cnt[ord(c) - ord('0')] += 1\n",
    "        for i in range(9, -1, -1):\n",
    "            ans += ''.join(chr(ord('0') + i) for _ in range(cnt[i] >> 1))\n",
    "        first = next((chr(ord('0') + i) for i in range(9, -1, -1) if cnt[i] & 1), '')\n",
    "        if not ans: return first\n",
    "        if ans[0] == '0': return first if first else '0'\n",
    "        return ans + first + ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(num)\n",
    "        if cnt['0'] == len(num):\n",
    "            return '0'\n",
    "        s = \"\"\n",
    "        d = digits[1:]\n",
    "        for i in d[::-1]:\n",
    "            s += str(i) * (cnt[i] // 2)\n",
    "        if s != '':\n",
    "            s += '0' * (cnt['0'] // 2)\n",
    "        t = s[::-1]\n",
    "        for i in digits[::-1]:\n",
    "            if cnt[i] % 2:\n",
    "                s += i\n",
    "                break\n",
    "        return s + t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "\n",
    "        num_count = [0] * 10\n",
    "\n",
    "        for i in num:\n",
    "            num_count[int(i)] += 1\n",
    "        \n",
    "        single_mid = ''\n",
    "        palin_left = ''\n",
    "        for i in range(9, -1, -1):\n",
    "            # single num choice\n",
    "            if num_count[i] % 2 == 1 and single_mid == '':\n",
    "                single_mid = str(i)\n",
    "            # double add\n",
    "            for _ in range(int(num_count[i] / 2)):\n",
    "                if i != 0:\n",
    "                    palin_left = palin_left + str(i)\n",
    "                if i == 0:\n",
    "                    if palin_left != '':\n",
    "                        palin_left = palin_left + str(i)\n",
    "\n",
    "        return palin_left + single_mid + palin_left[::-1] if palin_left != '' or single_mid != '' else '0'\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        # Counter(num) 可以统计每个字符出现的次数\n",
    "        cnt = Counter(num)     \n",
    "        # 特判\n",
    "        if cnt['0'] == len(num):\n",
    "            return \"0\"\n",
    "        # 初始化为空串\n",
    "        s = \"\"\n",
    "        # 构造左半边部分, 依次填充较大的字符\n",
    "        for d in digits[:0:-1]:\n",
    "            s += d * (cnt[d] // 2)\n",
    "        if s:\n",
    "            s += '0' * (cnt['0'] // 2)\n",
    "        \n",
    "        t = s[::-1]\n",
    "        # 中间如果还剩有数字的话，则填充剩下的\n",
    "        for d in digits[::-1]:\n",
    "            if cnt[d] % 2:\n",
    "                s += d\n",
    "                break\n",
    "        \n",
    "        return s + t\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnts = Counter(num)\n",
    "        if set(num) == {'0'}: return num[0] # 特殊情况 全0\n",
    "        ans = ''\n",
    "        mid = ''\n",
    "        for x in '9876543210':\n",
    "            fre = cnts[x]\n",
    "            a, b = divmod(fre, 2)\n",
    "            if mid == '' and b: mid = x # 第一个奇数频率x\n",
    "            if ans == '' and x == '0': continue # 前导零不添加\n",
    "            ans += a * x\n",
    "        return ans + mid + ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cot = Counter(num)\n",
    "        select = []\n",
    "        single_c = \"X\"\n",
    "        for k,v in cot.items():\n",
    "            if v%2==0:\n",
    "                select.append([k,v//2])\n",
    "            else:\n",
    "                if v>1:\n",
    "                    select.append([k,v//2])\n",
    "                single_c = k if single_c==\"X\" else max(single_c, k)\n",
    "                pass\n",
    "        \n",
    "        select.sort(reverse=True)\n",
    "        res = \"\"\n",
    "        if len(select)>0 and select[0][0]!='0':\n",
    "            for e in select:\n",
    "                res = res + ''.join([e[0]]*e[1])\n",
    "        if not single_c==\"X\":\n",
    "            res = res + single_c + res[::-1]\n",
    "        else:\n",
    "            res = res + res[::-1]\n",
    "        return res if res!=\"\" else \"0\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        d = [0 for i in range(10)]\n",
    "        for i in range(len(num)):\n",
    "            index = int(num[i])\n",
    "            d[index] += 1\n",
    "        \n",
    "        res = ''\n",
    "        for i in range(9,-1,-1):\n",
    "            for j in range(d[i]//2):\n",
    "                res += str(i)\n",
    "        ind = -1\n",
    "        # print(res)\n",
    "        for i in range(10):\n",
    "            if d[i]%2==1:\n",
    "                ind = max(ind,i)\n",
    "        if ind == -1:\n",
    "            if res[0] == '0':\n",
    "                return '0'\n",
    "            return res + res[::-1]\n",
    "        else:\n",
    "            if res == '':\n",
    "                return str(ind)\n",
    "            else:\n",
    "                if res[0] == '0':\n",
    "                    return str(ind)\n",
    "                else:\n",
    "                    return res+str(ind)+res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        c = Counter(num)\n",
    "        if len(c) == 1 and '0' in c:\n",
    "            return '0'\n",
    "        ans = mid = ''\n",
    "        for x in '9876543210':\n",
    "            if c[x] % 2 and mid == '': mid = x\n",
    "            ans += x * (c[x] // 2)\n",
    "        i = 0\n",
    "        while i < len(ans):\n",
    "            if ans[i] == '0':\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        ans = ans[i:]\n",
    "        return ans + mid + ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "      num = Counter(num)\n",
    "      before = \"\"\n",
    "      for c in \"9876543210\":\n",
    "        if c in num and num[c] >= 2:\n",
    "          before += c * (num[c] // 2)\n",
    "          num[c] -= 2 * (num[c] // 2)\n",
    "\n",
    "      before = \"\" if before and before[0] == \"0\" else before\n",
    "      mid = \"\"\n",
    "      for c in \"9876543210\":\n",
    "        if c in num and num[c] != 0:\n",
    "          mid = c\n",
    "          break\n",
    "\n",
    "      res = before + mid + \"\".join(list(reversed(before)))\n",
    "      return res if res else \"0\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        def get_str(n, idx):\n",
    "            c = chr(idx + ord('0'))\n",
    "            ans = \"\"\n",
    "            while n:\n",
    "                if n & 1:\n",
    "                    ans += c\n",
    "                c += c\n",
    "                n >>= 1\n",
    "            return ans\n",
    "\n",
    "        cnt = [0] * 10\n",
    "        for x in num:\n",
    "            i = ord(x) - ord('0')\n",
    "            cnt[i] += 1\n",
    "        ans = \"\"\n",
    "        for i in range(9, -1, -1):\n",
    "            if i == 0 and len(ans) == 0: break\n",
    "            ans += get_str(cnt[i] // 2, i)\n",
    "            cnt[i] -= cnt[i]//2 * 2\n",
    "        \n",
    "        last = \"\"\n",
    "        for i in range(9, -1, -1):\n",
    "            if cnt[i] > 0:\n",
    "                last = get_str(1, i)\n",
    "                break\n",
    "        return ans + last + ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = collections.Counter(num)\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for ele in '987654321':\n",
    "            if cnt[ele] >= 2:\n",
    "                res.extend(cnt[ele] // 2 * [ele])\n",
    "\n",
    "                if cnt[ele] % 2 == 0:\n",
    "                    del cnt[ele]\n",
    "                else:\n",
    "                    cnt[ele] = 1\n",
    "        \n",
    "        if not res:\n",
    "            return max(cnt)\n",
    "\n",
    "        for ele in '9876543210':\n",
    "            if cnt[ele] >= 2:\n",
    "                res.extend(cnt[ele] // 2 * [ele])\n",
    "            \n",
    "                if cnt[ele] % 2 == 0:\n",
    "                    del cnt[ele]\n",
    "                else:\n",
    "                    cnt[ele] = 1\n",
    "        \n",
    "        ans1 = ''.join(res)\n",
    "        ans2 = ans1[::-1]\n",
    "\n",
    "        for ele in '9876543210':\n",
    "            if cnt[ele] >= 1:\n",
    "                return ans1 + ele + ans2\n",
    "\n",
    "        return ans1 + ans2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        #if int(num.strip('0')) < 10: return num.strip('0')\n",
    "        ans, pro = \"\", \"\"\n",
    "        dic = dict(collections.Counter(num))\n",
    "        if len(dic) == 1 and '0' in dic: return '0'\n",
    "        dic2 = sorted(dic.items(), key=lambda x:(x[0]), reverse=True)\n",
    "        for ch in dic2:\n",
    "            if ch[1] % 2 == 0:\n",
    "                ans += ch[0] * (ch[1] // 2)\n",
    "            else:\n",
    "                if ch[1] > 2:\n",
    "                    ans += ch[0] * (ch[1] // 2)\n",
    "                pro += ch[0]\n",
    "        ans = ans.lstrip('0')\n",
    "        if pro == \"\":\n",
    "            return ans + ans[::-1]\n",
    "        else:\n",
    "            return ans + pro[0] + ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        m = defaultdict(int)\n",
    "        for c in num:\n",
    "            m[c] += 1\n",
    "        \n",
    "        res = \"\"\n",
    "        for i in range(9, -1, -1):\n",
    "\n",
    "            # 避免前导0\n",
    "            if i == 0 and res == \"\":\n",
    "                break\n",
    "                \n",
    "            cnt = m[str(i)] // 2\n",
    "\n",
    "            for j in range(cnt):\n",
    "                res += str(i)\n",
    "            \n",
    "            m[str(i)] -= 2*cnt\n",
    "        \n",
    "        res1 = res[::-1]\n",
    "\n",
    "        for i in range(9, -1, -1):\n",
    "            if m[str(i)] > 0:\n",
    "                res += str(i)\n",
    "                break\n",
    "        \n",
    "        return res + res1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        from collections import Counter\n",
    "        if False:\n",
    "            #condition:\n",
    "            if len(num)<=1 :\n",
    "                return num\n",
    "            #process odd/even\n",
    "            odd_nums = []\n",
    "            even_nums = []\n",
    "            for k,v in Counter(num).items():\n",
    "                print(k,v,num, even_nums, [int(k)]*(v//2))\n",
    "                if v % 2==0:\n",
    "                    even_nums.extend([int(k)]*(v//2))\n",
    "                else:\n",
    "                    odd_nums.append(int(k))\n",
    "                    if v>1:\n",
    "                        even_nums.extend([int(k)]*(v//2))\n",
    "\n",
    "            #combine num\n",
    "            even_nums.sort(reverse=True)\n",
    "            odd_nums = [max(odd_nums)] if odd_nums else []\n",
    "\n",
    "            print(odd_nums, even_nums)\n",
    "            print(type(set([0])))\n",
    "            if set(even_nums) == set([0]):\n",
    "                if odd_nums:\n",
    "                    return str(odd_nums[0])\n",
    "                else:\n",
    "                    return \"0\"\n",
    "            else:\n",
    "                result =  even_nums + odd_nums + even_nums[::-1]\n",
    "                return \"\".join(map(lambda s: str(s), result))\n",
    "        else:\n",
    "            nums1 =  [(k, v//2) for k, v in Counter(num).items() if v >=2]\n",
    "            nums2 =  [k for k, v in Counter(num).items() if v %2 != 0]\n",
    "            nums1.sort(key=lambda x: int(x[0]), reverse=True)\n",
    "            print(nums1)\n",
    "            result = \"\"\n",
    "            for k,v in nums1:\n",
    "                result += k*v\n",
    "            nums2 = max(nums2) if nums2 else \"\"\n",
    "            if set(result) != set('0'):\n",
    "                result = result + nums2 + result[::-1]\n",
    "            else:\n",
    "                result = nums2\n",
    "            result = result if result else \"0\"\n",
    "            return result\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(list(num))\n",
    "        arr = [(-int(k), v) for k,v in cnt.items()]\n",
    "        #arr.sort(key=lambda x : -x[0])\n",
    "        heapq.heapify(arr)\n",
    "        s = '' \n",
    "        arr2 = []\n",
    "        while arr:\n",
    "            k, v = heapq.heappop(arr) \n",
    "            if v == 1:\n",
    "                heapq.heappush(arr2, (k, v))\n",
    "            else:\n",
    "                if len(s) > 0 or k != 0 :\n",
    "                    s += str(-k) * (v//2) \n",
    "                if v % 2==1:\n",
    "                    heapq.heappush(arr2, (k, 1)) \n",
    "        if arr2:\n",
    "            k, v = heapq.heappop(arr2) \n",
    "            s = s + str(-k) + s[::-1]\n",
    "        else:\n",
    "            s = s + s[::-1]\n",
    "        return s if s != '' else '0'\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef largestPalindromic(self, num: str) -> str:\n",
    "\t\tcounters = collections.Counter(num)\n",
    "\t\t# 分奇偶，奇数只能存在一个，用字符串就行，偶数用列表存着\n",
    "\t\tlis = []\n",
    "\t\tmid = -1\n",
    "\t\tresult = ''\n",
    "\t\t# for item in counters.items():\n",
    "\t\t# \tif item[1] %2 == 0:\n",
    "\t\t# \t\tlis.append(item)\n",
    "\t\t# \telse:\n",
    "\t\t# \t\todd = odd if int(odd) > int(str(item[0]) * item[1]) else str(item[0]) * item[1]\n",
    "\t\tfor item in counters.items():\n",
    "\t\t\tlis.append(item)\n",
    "\t\tlis.sort(key=lambda item: (item[0], item[1]), reverse=True)\n",
    "\t\tprint('=' * 20)\n",
    "\t\tprint(lis)\n",
    "\t\tleft = ''\n",
    "\t\tright = ''\n",
    "\t\tfor item in lis:\n",
    "\t\t\ttemp = str(item[0]) * (item[1] // 2)\n",
    "\t\t\tleft += temp\n",
    "\t\t\tright = temp + right\n",
    "\t\t\tis_odd_even = item[1] % 2\n",
    "\t\t\tif is_odd_even != 0:\n",
    "\t\t\t\tmid = mid if mid > int(item[0]) else int(item[0])\n",
    "\t\tprint(mid)\n",
    "\t\tif mid >= 0 :\n",
    "\t\t\tresult += left + str(mid) + right\n",
    "\t\telse :\n",
    "\t\t\tresult += left + right\n",
    "\t\tresult = result.strip('0')\n",
    "\t\tprint(left)\n",
    "\t\tprint(right)\n",
    "\t\tprint(result)\n",
    "\t\treturn result if result else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        record = [0]*10\n",
    "        for ch in num:\n",
    "            record[int(ch)] += 1\n",
    "\n",
    "        res = []\n",
    "        for i in range(9, -1, -1):\n",
    "            if (i==0 and len(res) and record[0]) or (i>0 and record[i]):\n",
    "                for j in range(record[i]//2):\n",
    "                    res.append(i)\n",
    "\n",
    "        flag = False\n",
    "        for i in range(9, -1, -1):\n",
    "            if record[i]%2==1:\n",
    "                flag = True\n",
    "                res.append(i)\n",
    "                break\n",
    "        \n",
    "        if len(res)==0:\n",
    "            return \"0\"\n",
    "        if res and res[0]==0:\n",
    "            return \"0\"\n",
    "\n",
    "        size = len(res)-2 if flag else len(res)-1\n",
    "        for i in range(size, -1, -1):\n",
    "            res.append(res[i])\n",
    "\n",
    "        ans = \"\"\n",
    "        for x in res:\n",
    "            ans = ans+str(x)\n",
    "\n",
    "        index = 0\n",
    "        while index<len(ans) and ans[index]=='0':\n",
    "            index += 1\n",
    "        if index==0:\n",
    "            return ans\n",
    "        if ans[index:-index]==\"\":\n",
    "            return \"0\"\n",
    "        return ans[index:-index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        nums_hash = {}\n",
    "        for i in range(len(num)):\n",
    "            if num[i] not in nums_hash:\n",
    "                nums_hash[num[i]] = 0\n",
    "            nums_hash[num[i]] += 1\n",
    "        new_str = ''\n",
    "        for i in range(9, -1, -1):\n",
    "            if str(i) in nums_hash:\n",
    "                t = nums_hash[str(i)] // 2\n",
    "                if i == 0 and len(new_str) == 0:\n",
    "                    break\n",
    "                for _ in range(t):\n",
    "                    new_str += str(i)\n",
    "                nums_hash[str(i)] -= t * 2\n",
    "        new_str_2 = new_str[::-1]\n",
    "        for i in range(9, -1, -1):\n",
    "            if str(i) in nums_hash and nums_hash[str(i)] != 0:\n",
    "                new_str += str(i)\n",
    "                break\n",
    "\n",
    "        return new_str + new_str_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = [0] * 10\n",
    "        for c in num:\n",
    "            cnt[ord(c) - ord('0')] += 1\n",
    "        ans = []\n",
    "        for i in range(9, -1, -1):\n",
    "            ans += [chr(ord('0') + i) for _ in range(cnt[i] >> 1)]\n",
    "        first = next((chr(ord('0') + i) for i in range(9, -1, -1) if cnt[i] & 1), '')\n",
    "        if not ans: return first\n",
    "        if ans[0] == '0': return first if first else '0'\n",
    "        return ''.join(ans) + first + ''.join(reversed(ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(list(num))\n",
    "        arr = [(-int(k), v) for k,v in cnt.items()]\n",
    "        #arr.sort(key=lambda x : -x[0])\n",
    "        heapq.heapify(arr)\n",
    "        s = '' \n",
    "        arr2 = []\n",
    "        while arr:\n",
    "            k, v = heapq.heappop(arr) \n",
    "            if v == 1:\n",
    "                heapq.heappush(arr2, (k, v))\n",
    "            else:\n",
    "                if len(s) > 0 or k != 0 :\n",
    "                    s += str(-k) * (v//2) \n",
    "                if v % 2==1:\n",
    "                    heapq.heappush(arr2, (k, 1)) \n",
    "        if arr2:\n",
    "            k, v = heapq.heappop(arr2) \n",
    "            s = s + str(-k) + s[::-1]\n",
    "        else:\n",
    "            s = s + s[::-1]\n",
    "        return s if s != '' else '0'\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "    \t\t\t\tans = []\n",
    "    \t\t\t\tcnt = Counter(num)\n",
    "    \t\t\t\tif cnt['0'] == len(num):\n",
    "    \t\t\t\t\t\t\t\treturn '0'\n",
    "    \t\t\t\t#print(f'cnt:{cnt}')\n",
    "    \t\t\t\tuseZero = any(cnt[x] > 1 for x in '123456789')\n",
    "    \t\t\t\t#print(f'useZero:{useZero}')\n",
    "    \t\t\t\tfor x in '9876543210':\n",
    "    \t\t\t\t\t\t\t\tif x == '0' and not ans:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tcontinue\n",
    "    \t\t\t\t\t\t\t\tif x in cnt:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tt = cnt[x] // 2\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tans.extend([x] * t)\n",
    "    \t\t\t\trans = ans[::-1]\n",
    "    \t\t\t\tfor x in '9876543210':\n",
    "    \t\t\t\t\t\t\t\tif cnt[x] % 2:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tans.append(x)\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tbreak\n",
    "    \t\t\t\tans.extend(rans)\n",
    "    \t\t\t\treturn ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        if len(num) == 0:\n",
    "            return \"\"\n",
    "        mapn = defaultdict(int)\n",
    "        list(num)\n",
    "        a = []\n",
    "        for i in num:\n",
    "            mapn[i] += 1\n",
    "            if mapn[i]%2 == 0:\n",
    "                a.append(i)\n",
    "        MAX = -1\n",
    "        for key,value in mapn.items():\n",
    "            if value%2 == 1:\n",
    "                MAX = max(int(key),MAX)\n",
    "        \n",
    "        b = \"\".join(sorted(a,reverse=-1))\n",
    "        while True:\n",
    "            if len(b)>0 and b[0]=='0':\n",
    "                b = b[1:]\n",
    "            else:\n",
    "                break\n",
    "        if len(b)==0:\n",
    "            return str(MAX) if MAX >= 0 else \"0\"\n",
    "        \n",
    "        a = b[::-1]  \n",
    "        return b+str(MAX)+a if MAX >= 0 else b+a "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "    \t\t\t\tans = []\n",
    "    \t\t\t\tcnt = Counter(num)\n",
    "    \t\t\t\tif all(cnt[x] == 0 for x in '123456789'):\n",
    "    \t\t\t\t\t\t\t\treturn '0'\n",
    "    \t\t\t\t#print(f'cnt:{cnt}')\n",
    "    \t\t\t\tmid = None\n",
    "    \t\t\t\tfor x in '9876543210':\n",
    "    \t\t\t\t\t\t\t\tif cnt[x] % 2:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tmid = x\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tbreak\n",
    "    \t\t\t\tuseZero = any(cnt[x] > 1 for x in '123456789')\n",
    "    \t\t\t\t#print(f'useZero:{useZero}')\n",
    "    \t\t\t\tfor x in '9876543210':\n",
    "    \t\t\t\t\t\t\t\tif x == '0' and not useZero:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tcontinue\n",
    "    \t\t\t\t\t\t\t\tif x in cnt:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tt = cnt[x] // 2\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tans.extend([x] * t)\n",
    "    \t\t\t\tif mid:\n",
    "    \t\t\t\t\t\t\t\tans.append(mid)\n",
    "    \t\t\t\tfor x in '0123456789':\n",
    "    \t\t\t\t\t\t\t\tif x == '0' and not useZero:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tcontinue\n",
    "    \t\t\t\t\t\t\t\tif x in cnt:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tt = cnt[x] // 2\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tans.extend([x] * t)\n",
    "    \t\t\t\treturn ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "    \t\t\t\tans = []\n",
    "    \t\t\t\tcnt = Counter(num)\n",
    "    \t\t\t\tif cnt['0'] == len(num):\n",
    "    \t\t\t\t\t\t\t\treturn '0'\n",
    "    \t\t\t\tfor x in '9876543210':\n",
    "    \t\t\t\t\t\t\t\tif x == '0' and not ans:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tcontinue\n",
    "    \t\t\t\t\t\t\t\tif x in cnt:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tt = cnt[x] // 2\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tans.extend([x] * t)\n",
    "    \t\t\t\trans = ans[::-1]\n",
    "    \t\t\t\tfor x in '9876543210':\n",
    "    \t\t\t\t\t\t\t\tif cnt[x] % 2:\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tans.append(x)\n",
    "    \t\t\t\t\t\t\t\t\t\t\t\tbreak\n",
    "    \t\t\t\tans.extend(rans)\n",
    "    \t\t\t\treturn ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        num=str(num)\n",
    "        k=list(num)\n",
    "        f=[-1]*10\n",
    "        q=Counter(k)\n",
    "        for x in range(0,10):\n",
    "            if str(x) in q:\n",
    "                \n",
    "                f[x]=q[str(x)]\n",
    "    \n",
    "               \n",
    "        m=-1\n",
    "        s=\"\"\n",
    "        for i in range(9,-1,-1):\n",
    "            if f[i]==-1:\n",
    "                continue\n",
    "            if f[i]%2:\n",
    "              if i>m: \n",
    "               m=i\n",
    "            t=f[i]//2   \n",
    "            while t:\n",
    "               s+=str(i)\n",
    "               t-=1\n",
    "        \n",
    "        if m!=-1:\n",
    "         s+=str(m)   \n",
    "         ans=s+s[0:-1][::-1]\n",
    "        else:\n",
    "         ans=s+s[::-1]    \n",
    "        l=0\n",
    "        while l<=(len(ans)//2):\n",
    "            if ans[l]=='0':\n",
    "                l+=1\n",
    "            else:\n",
    "               break      \n",
    "        e=ans[l:len(ans)-l]\n",
    "        return e if e!=\"\" else '0'        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        if num.count(\"0\")==len(num):\n",
    "            return \"0\"\n",
    "        h=-1\n",
    "        num=list(map(int,num))\n",
    "        d={}\n",
    "        ans=\"\"\n",
    "        sum0=0\n",
    "        for i in num:\n",
    "            d[i]=d.get(i,0)+1\n",
    "        for i in range(0,10):\n",
    "            if i not in d:\n",
    "                d[i]=0\n",
    "        for i in range(9,0,-1):\n",
    "            if d[i]%2==0 and d[i]>=2:\n",
    "                ans += str(i) * (d[i]//2)\n",
    "                sum0+=d[i]\n",
    "                d[i]=0\n",
    "            if d[i]%2==1 and d[i]>2:\n",
    "                ans +=str(i) * ((d[i] - 1)//2)\n",
    "                sum0+=d[i]-1\n",
    "                d[i]=1\n",
    "        if sum0!=0 :\n",
    "            if d[0]>=2 and d[0]%2==0:\n",
    "                ans+=\"0\" * (d[0]//2)\n",
    "                d[0]=0\n",
    "            if d[0]>2 and d[0]%2==1:\n",
    "                ans+=\"0\" * ((d[0] - 1)//2)\n",
    "                d[0]=1\n",
    "        for i in range(9,-1,-1):\n",
    "            if d[i]==1:\n",
    "                h=str(i)\n",
    "                break\n",
    "        ans1=ans[::-1]\n",
    "        if h !=-1:\n",
    "            ans+=h\n",
    "        return ans+ans1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = Counter(num)\n",
    "\n",
    "        ret = []\n",
    "\n",
    "        ks = sorted(list(cnt.keys()), reverse=True)\n",
    "\n",
    "        for k in ks:\n",
    "            while cnt[k] > 1:\n",
    "                if k == '0' and len(ret) == 0:\n",
    "                    break\n",
    "\n",
    "                ret.append(k)\n",
    "                cnt[k] -= 2\n",
    "\n",
    "        for k in ks:\n",
    "            if cnt[k] > 0:\n",
    "                ret = ret + [k] + ret[::-1]\n",
    "                break\n",
    "\n",
    "        else:\n",
    "            ret = ret + ret[::-1]\n",
    "\n",
    "        return ''.join(ret)\n",
    "\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def largestPalindromic(self, num: str) -> str:\r\n",
    "        n = len(num)\r\n",
    "\r\n",
    "        cnt = defaultdict(int)\r\n",
    "\r\n",
    "        for c in num:\r\n",
    "            cnt[c] += 1\r\n",
    "\r\n",
    "        if len(cnt) == 1 or n == 1:\r\n",
    "            if num[0] == '0':\r\n",
    "                return '0'\r\n",
    "\r\n",
    "            return num\r\n",
    "\r\n",
    "        select = {}\r\n",
    "        zeros = 0\r\n",
    "\r\n",
    "        for c, v in cnt.items():\r\n",
    "            if c == '0':\r\n",
    "                zeros = v if v % 2 == 0 else v - 1\r\n",
    "                continue\r\n",
    "\r\n",
    "            if v % 2 == 0:\r\n",
    "                select[c] = v\r\n",
    "            elif v > 1 and v % 2 == 1:\r\n",
    "                select[c] = v - 1\r\n",
    "\r\n",
    "        odd = None\r\n",
    "        for c, v in cnt.items():\r\n",
    "            if v % 2 == 1:\r\n",
    "                if odd is None:\r\n",
    "                    odd = c\r\n",
    "                else:\r\n",
    "                    odd = max(odd, c)\r\n",
    "\r\n",
    "        ret = []\r\n",
    "\r\n",
    "        # print('!')\r\n",
    "\r\n",
    "        # print(select, zeros, odd)\r\n",
    "\r\n",
    "        for c in sorted(list(select.keys()), reverse=True):\r\n",
    "            v = select[c]\r\n",
    "            ret.extend([c] * (v // 2))\r\n",
    "\r\n",
    "        # print(ret)\r\n",
    "\r\n",
    "        if len(ret) > 0:\r\n",
    "            ret.extend(['0'] * (zeros // 2))\r\n",
    "\r\n",
    "        # print(ret)\r\n",
    "\r\n",
    "        if odd is not None:\r\n",
    "            ret = ret + [odd] + list(reversed(ret))\r\n",
    "        else:\r\n",
    "            ret = ret + list(reversed(ret))\r\n",
    "\r\n",
    "        # print(ret)\r\n",
    "\r\n",
    "        return ''.join(ret)\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def largestPalindromic(self, num: str) -> str:\r\n",
    "        n = len(num)\r\n",
    "\r\n",
    "        cnt = defaultdict(int)\r\n",
    "\r\n",
    "        for c in num:\r\n",
    "            cnt[c] += 1\r\n",
    "\r\n",
    "        if len(cnt) == 1 or n == 1:\r\n",
    "            if num[0] == '0':\r\n",
    "                return '0'\r\n",
    "\r\n",
    "            return num\r\n",
    "\r\n",
    "        select = {}\r\n",
    "        zeros = 0\r\n",
    "\r\n",
    "        for c, v in cnt.items():\r\n",
    "            if c == '0':\r\n",
    "                zeros = v if v % 2 == 0 else v - 1\r\n",
    "                continue\r\n",
    "\r\n",
    "            if v % 2 == 0:\r\n",
    "                select[c] = v\r\n",
    "            elif v > 1 and v % 2 == 1:\r\n",
    "                select[c] = v - 1\r\n",
    "\r\n",
    "        odd = None\r\n",
    "        for c, v in cnt.items():\r\n",
    "            if v % 2 == 1:\r\n",
    "                if odd is None:\r\n",
    "                    odd = c\r\n",
    "                else:\r\n",
    "                    odd = max(odd, c)\r\n",
    "\r\n",
    "        ret = []\r\n",
    "\r\n",
    "        print('!')\r\n",
    "\r\n",
    "        print(select, zeros, odd)\r\n",
    "\r\n",
    "        for c in sorted(list(select.keys()), reverse=True):\r\n",
    "            v = select[c]\r\n",
    "            ret.extend([c] * (v // 2))\r\n",
    "\r\n",
    "        print(ret)\r\n",
    "\r\n",
    "        if len(ret) > 0:\r\n",
    "            ret.extend(['0'] * (zeros // 2))\r\n",
    "\r\n",
    "        print(ret)\r\n",
    "\r\n",
    "        if odd is not None:\r\n",
    "            ret = ret + [odd] + list(reversed(ret))\r\n",
    "        else:\r\n",
    "            ret = ret + list(reversed(ret))\r\n",
    "\r\n",
    "        print(ret)\r\n",
    "\r\n",
    "        return ''.join(ret)\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        data={}\n",
    "        for i in range(len(num)):\n",
    "            n=int(num[i])\n",
    "            if n not in data:\n",
    "                data[n]=0\n",
    "            data[n]+=1\n",
    "        tmp=[]\n",
    "        max1=-1\n",
    "        for i in range(9,0,-1):\n",
    "            if i in data:\n",
    "                for j in range(int(data[i]/2)):\n",
    "                    tmp.append(str(i))\n",
    "                if data[i]%2==1:\n",
    "                    max1=max(max1,i)\n",
    "        if len(tmp)==0:\n",
    "            if max1!=-1:\n",
    "                return str(max1)\n",
    "            else:\n",
    "                return \"0\"\n",
    "        elif 0 in data:\n",
    "            for j in range(int(data[0]/2)):\n",
    "                tmp.append(\"0\")\n",
    "            if data[0]%2==1:\n",
    "                    max1=max(max1,0)\n",
    "        if max1!=-1:\n",
    "            return \"\".join(tmp)+str(max1)+\"\".join(tmp[::-1])\n",
    "        else:\n",
    "            return \"\".join(tmp)+\"\".join(tmp[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        cnt = defaultdict(int)\n",
    "        for n in num:\n",
    "            cnt[n]+=1\n",
    "        print(cnt)\n",
    "        res = []\n",
    "        for i in range(10):\n",
    "            for j in range(cnt[str(i)]//2):\n",
    "                res.insert(0,str(i))\n",
    "        if res and res[0]=='0':\n",
    "            res = []\n",
    "        for i in range(9,-1,-1):\n",
    "            if cnt[str(i)]%2:\n",
    "                return \"\".join(res+[str(i)]+res[::-1])\n",
    "        if res:\n",
    "            return \"\".join(res+res[::-1])\n",
    "        else:\n",
    "            return '0'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import defaultdict\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        # 4479744\n",
    "        # 数字最大 bab; bb ; b\n",
    "        # dict=d[4]=4 d[7]=2, d[1]=1 d[3]=1 d[9]=1\n",
    "        # d[4] = [4], d[2] = [7], d[1]=[9,3,1]\n",
    "        # 按照出现次数和数字大小进行排列组合，看是否符合回文\n",
    "        # 生成回文 -> 选最大回文 生成括号全排列4 s==s[::-1]:回文\n",
    "        max_num = 0\n",
    "        used = Counter()\n",
    "        n=len(num)\n",
    "        occur = defaultdict(int)\n",
    "        for i in num:\n",
    "            occur[int(i)] += 1\n",
    "        keys = occur.keys()\n",
    "        i,j = 0, n-1\n",
    "        #贪心算法 从最大到最小 优先找偶数值 然后生成奇数值里最大的\n",
    "        res = [\"\"] * n\n",
    "        #print(occur)\n",
    "        total_cnt = 0\n",
    "        for nu in range(9, -1, -1):\n",
    "            if i==0 and nu == 0:\n",
    "                    continue\n",
    "            if occur[nu]>1:\n",
    "                #怎么生成新的数？\n",
    "                cnt = 0\n",
    "                orig_cnt = occur[nu]\n",
    "                while cnt < (orig_cnt // 2)*2: #对>=2的偶数组和3/5这样的奇数组\n",
    "                    res[i] = str(nu)\n",
    "                    res[j] = str(nu)\n",
    "                    i+=1\n",
    "                    j-=1\n",
    "                    cnt += 2\n",
    "                    occur[nu] -= 2\n",
    "                total_cnt += cnt\n",
    "        if total_cnt == n:\n",
    "            return \"\".join(res)\n",
    "        for nu in range(9, -1, -1):         \n",
    "            if occur[nu] == 1: #赛中间\n",
    "                res[i] = str(nu)\n",
    "                occur[nu] -= 1\n",
    "                return \"\".join(res)\n",
    "        return \"0\"\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import defaultdict\n",
    "    def largestPalindromic(self, num: str) -> str:\n",
    "        # 4479744\n",
    "        # 数字最大 bab; bb ; b\n",
    "        # dict=d[4]=4 d[7]=2, d[1]=1 d[3]=1 d[9]=1\n",
    "        # d[4] = [4], d[2] = [7], d[1]=[9,3,1]\n",
    "        # 按照出现次数和数字大小进行排列组合，看是否符合回文\n",
    "        # 生成回文 -> 选最大回文 生成括号全排列4 s==s[::-1]:回文\n",
    "        max_num = 0\n",
    "        used = Counter()\n",
    "        n=len(num)\n",
    "        occur = defaultdict(int)\n",
    "        for i in num:\n",
    "            occur[int(i)] += 1\n",
    "        keys = occur.keys()\n",
    "        i,j = 0, n-1\n",
    "        #贪心算法 从最大到最小 优先找偶数值 然后生成奇数值里最大的\n",
    "        res = [\"\"] * n\n",
    "        print(occur)\n",
    "        total_cnt = 0\n",
    "        for nu in range(9, -1, -1):\n",
    "            if i==0 and nu == 0:\n",
    "                    continue\n",
    "            if occur[nu]>1 and occur[nu] % 2 == 0:\n",
    "                #怎么生成新的数？\n",
    "                cnt = 0\n",
    "                orig_cnt = occur[nu]\n",
    "                while cnt < orig_cnt:\n",
    "                    res[i] = str(nu)\n",
    "                    res[j] = str(nu)\n",
    "                    i+=1\n",
    "                    j-=1\n",
    "                    cnt += 2\n",
    "                    occur[nu] -= 2\n",
    "                total_cnt += cnt\n",
    "            elif occur[nu]>1 and occur[nu] % 2 > 0: #5\n",
    "                cnt = 0\n",
    "                orig_cnt = occur[nu]\n",
    "                while cnt < orig_cnt // 2:\n",
    "                    res[i] = str(nu)\n",
    "                    res[j] = str(nu)\n",
    "                    i+=1\n",
    "                    j-=1\n",
    "                    cnt += 1\n",
    "                    occur[nu] -= 2\n",
    "                    total_cnt += 2\n",
    "\n",
    "        if total_cnt == n:\n",
    "            return \"\".join(res)\n",
    "        for nu in range(9, -1, -1):         \n",
    "            if occur[nu] == 1: #赛中间\n",
    "                res[i] = str(nu)\n",
    "                occur[nu] -= 1\n",
    "                return \"\".join(res)\n",
    "        return \"0\"\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
